// 求解欧拉函数
// 欧拉函数（Euler's totient function），即 phi(n)，表示的是小于等于 n 和 n 互质的数的个数。
// 比如说 phi(1) = 1
// 当 n 是质数的时候，显然有 phi(n) = n - 1
// 测试链接 ：https://www.spoj.com/problems/ETF/
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16693390.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/euler-totient/
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000001;
int cnt;
int prime[MAXN];
bool visited[MAXN];
int phi[MAXN];

// 试除法求欧拉函数
// 返回 phi[n]
int phi1(int n)
{
    long ans = n; // 使用 long 避免溢出
    for(int i = 2; i <= n / i; ++i)
    {
        // i 是质数
        if(n % i == 0)
        {
            ans = ans * (i - 1) / i;
        }
        // 除尽 i 这个质因子
        while(n % i == 0) n /= i;
    }
    if(n > 1) ans = ans * (n - 1) / n;
    return ans;
}

// 线性筛法求欧拉函数
// 生成 phi 表，时间复杂度 O(n)
void phi2(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        // i 是质数
        if(!visited[i])
        {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; 1LL * i * prime[j] <= n; ++j)
        {
            // prime[j] 是 m 的最小质因子
            int m = i * prime[j];
            visited[m] = true; // m 是合数
            if(i % prime[j] == 0)
            {
                // prime[j] 也是 i 的最小质因子
                // i 包含了 m 的所有质因子
                phi[m] = prime[j] * phi[i];
                break;
            }
            else
            {
                // 利用积性函数的性质
                // phi(m) = phi(prime[j] * i) = phi(prime[j]) * phi(i)
                phi[m] = (prime[j] - 1) * phi[i];
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    phi2(MAXN - 1);
    for(int i = 0, m; i < n; ++i)
    {
        scanf("%d", &m);
        printf("%d\n", phi[m]);
    }

    return 0;
}